package day_2022_12_to_3.year2023;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2023/03/21 19:49
 **/
public class Day3_21_Review {
    class Solution1 {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            if(matrix.length == 0 || matrix[0].length == 0) return false;
            int m = matrix.length, n = matrix[0].length;
            int i = 0, j = n-1;
            while(i < m && j >= 0) {
                if(matrix[i][j] > target) j--;
                else if(matrix[i][j] < target) i++;
                else return true;
            }
            return false;
        }
    }

    class Solution2 {
        public String replaceSpace(String s) {
            StringBuffer sb = new StringBuffer();
            for(char c : s.toCharArray()) {
                sb.append(c == ' ' ? "%20" : c);
            }
            return sb.toString();
        }
    }

    class Solution3 {
        public int[] reversePrint(ListNode head) {
            if(head == null) return new int[0];
            Deque<Integer> s = new LinkedList<>();
            while(head != null) {
                s.push(head.val);
                head = head.next;
            }
            return s.stream().mapToInt(Integer::intValue).toArray();
        }
    }

    class Solution4 {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeHelper(preorder, inorder, 0, preorder.length - 1);
        }

        int post = 0;
        public TreeNode buildTreeHelper(int[] pre, int [] inor, int l, int r) {
            if(post == pre.length || l > r) return null;
            TreeNode cur = new TreeNode(pre[post]);
            int index = findInInor(pre[post], inor);
            post++;
            cur.left = buildTreeHelper(pre, inor, l, index-1);
            cur.right = buildTreeHelper(pre, inor, index+1, r);
            return cur;
        }

        public int findInInor(int k, int[] inor) {
            for(int i = 0; i < inor.length; ++i)
                if(k == inor[i]) return i;
            return -1;
        }
    }

    class Solution5 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) return null;
            if(root == p || root == q) return root;
            TreeNode l = lowestCommonAncestor(root.left, p, q);
            TreeNode r = lowestCommonAncestor(root.right, p, q);
            if(l == null && r != null) return r;
            else if(l != null && r == null) return l;
            else if(l == null && r == null) return null;
            else return root;
        }
    }

    class Solution6 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) return root;
            if(root == p || root == q) return root;
            if(root.val < p.val && root.val < q.val) {
                return lowestCommonAncestor(root.right, p, q);
            }else if(root.val > p.val && root.val > q.val) {
                return lowestCommonAncestor(root.left, p, q);
            }else return root;
        }
    }
}